/*-------------------------------------------------------------------------
 *
 * array_typanalyze.c
 *	  从数组列中收集统计信息的函数
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/utils/adt/array_typanalyze.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/detoast.h"
#include "commands/vacuum.h"
#include "utils/array.h"
#include "utils/builtins.h"
#include "utils/datum.h"
#include "utils/lsyscache.h"
#include "utils/typcache.h"


/*
 * 为了避免在分析过程中消耗过多的内存、IO 和 CPU 负载，
 * 和/或在生成的 pg_statistic 行中占用过多空间，我们忽略宽度超过 ARRAY_WIDTH_THRESHOLD 的数组
 * （在去气化之后！）。请注意，这个数字比分析.c 的标准 typanalyze 代码中
 * 使用的类似 WIDTH_THRESHOLD 限制要大得多。
 */
#define ARRAY_WIDTH_THRESHOLD 0x10000

/* compute_array_stats 函数的额外数据 */
typedef struct
{
	/* 关于数组元素类型的信息 */
	Oid			type_id;		/* 元素类型的 OID */
	Oid			eq_opr;			/* 默认相等运算符的 OID */
	Oid			coll_id;		/* 要使用的排序 */
	bool		typbyval;		/* 元素类型的物理属性 */
	int16		typlen;
	char		typalign;

	/*
	 * 元素类型的比较和哈希函数的查找数据（这些在
	 * 类型的 typcache 条目中，我们希望在 ANALYZE 运行的整个生命周期内保持有效）
	 */
	FmgrInfo   *cmp;
	FmgrInfo   *hash;

	/* 来自 std_typanalyze() 的保存状态 */
	AnalyzeAttrComputeStatsFunc std_compute_stats;
	void	   *std_extra_data;
} ArrayAnalyzeExtraData;

/*
 * 当 compute_array_stats 正在运行时，我们在此处保留对额外数据的指针
 * 以供各种子例程使用。compute_array_stats 当前不需要重入，所以避免这个也
 * 不值得额外的符号繁琐。
 */
static ArrayAnalyzeExtraData *array_extra_data;

/* lossy counting 算法的哈希表条目 */
typedef struct
{
	Datum		key;			/* 这是 LC 算法中的 'e'。 */
	int			frequency;		/* 这是 'f'。 */
	int			delta;			/* 这是 'delta'。 */
	int			last_container; /* 用于去重数组元素。 */
} TrackItem;

/* 用于不同元素计数的哈希表条目 */
typedef struct
{
	int			count;			/* 数组中的不同元素计数 */
	int			frequency;		/* 看到这个计数的数组数量 */
} DECountItem;

static void fc_compute_array_stats(VacAttrStats *fc_stats,
								AnalyzeAttrFetchFunc fc_fetchfunc, int fc_samplerows, double fc_totalrows);
static void fc_prune_element_hashtable(HTAB *fc_elements_tab, int fc_b_current);
static uint32 fc_element_hash(const void *fc_key, Size fc_keysize);
static int	fc_element_match(const void *fc_key1, const void *fc_key2, Size fc_keysize);
static int	fc_element_compare(const void *fc_key1, const void *fc_key2);
static int	fc_trackitem_compare_frequencies_desc(const void *fc_e1, const void *fc_e2, void *fc_arg);
static int	fc_trackitem_compare_element(const void *fc_e1, const void *fc_e2, void *fc_arg);
static int	fc_countitem_compare_count(const void *fc_e1, const void *fc_e2, void *fc_arg);


/*
 * array_typanalyze -- array 列的 typanalyze 函数
 */
Datum array_typanalyze(PG_FUNCTION_ARGS)
{
	VacAttrStats *fc_stats = (VacAttrStats *) PG_GETARG_POINTER(0);
	Oid			fc_element_typeid;
	TypeCacheEntry *fc_typentry;
	ArrayAnalyzeExtraData *fc_extra_data;

	/*
	 * 调用标准的 typanalyze 函数。它可能无法找到所需的操作符，
	 * 在这种情况下我们也无能为力，因此直接失败。
	 */
	if (!std_typanalyze(fc_stats))
		PG_RETURN_BOOL(false);

	/*
	 * 检查属性数据类型是否为 varlena 数组（或其域）。
	 */
	fc_element_typeid = get_base_element_type(fc_stats->attrtypid);
	if (!OidIsValid(fc_element_typeid))
		elog(ERROR, "array_typanalyze was invoked for non-array type %u",
			 fc_stats->attrtypid);

	/*
	 * 收集关于元素类型的信息。如果无法找到某些内容，
	 * 则返回并保持 std_typanalyze() 的状态不变。
	 */
	fc_typentry = lookup_type_cache(fc_element_typeid,
								 TYPECACHE_EQ_OPR |
								 TYPECACHE_CMP_PROC_FINFO |
								 TYPECACHE_HASH_PROC_FINFO);

	if (!OidIsValid(fc_typentry->eq_opr) ||
		!OidIsValid(fc_typentry->cmp_proc_finfo.fn_oid) ||
		!OidIsValid(fc_typentry->hash_proc_finfo.fn_oid))
		PG_RETURN_BOOL(true);

	/* 存储我们的发现以供 compute_array_stats() 使用 */
	fc_extra_data = (ArrayAnalyzeExtraData *) palloc(sizeof(ArrayAnalyzeExtraData));
	fc_extra_data->type_id = fc_typentry->type_id;
	fc_extra_data->eq_opr = fc_typentry->eq_opr;
	fc_extra_data->coll_id = fc_stats->attrcollid;	/* 应该使用的排序规则 */
	fc_extra_data->typbyval = fc_typentry->typbyval;
	fc_extra_data->typlen = fc_typentry->typlen;
	fc_extra_data->typalign = fc_typentry->typalign;
	fc_extra_data->cmp = &fc_typentry->cmp_proc_finfo;
	fc_extra_data->hash = &fc_typentry->hash_proc_finfo;

	/* 保存旧的 compute_stats 和用于标量统计的 extra_data ... */
	fc_extra_data->std_compute_stats = fc_stats->compute_stats;
	fc_extra_data->std_extra_data = fc_stats->extra_data;

	/* ... 并用我们的信息替换它 */
	fc_stats->compute_stats = fc_compute_array_stats;
	fc_stats->extra_data = fc_extra_data;

	/*
	 * 请注意，我们将 stats->minrows 保持为 std_typanalyze 设置的值。
	 * 它在进行数组分析时是否应该增加？
	 */

	PG_RETURN_BOOL(true);
}

/*
 * compute_array_stats() -- 为数组列计算统计信息
 *
 * 此函数计算对确定数组操作符 <@、&& 和 @> 的选择性有用的统计信息。
 * 它通过 ANALYZE 在收集样本行后通过 compute_stats 钩子被调用。
 *
 * 我们还调用标准的 compute_stats 函数，它将计算与 btree 风格数组比较操作符相关的
 * “标量”统计信息。然而，尽管许多数组共享单个元素，整个数组的精确重复可能比较少见。
 * 这尤其困扰到长数组，由于 analyze.c 中使用的低 WIDTH_THRESHOLD，这些数组也可能缺乏所有标量统计信息。
 * 因此，除了标准统计信息，我们还找到最常见的数组元素并计算不同元素计数的直方图。
 *
 * 使用的算法是 Lossy Counting，如 G. S. Manku 和 R. Motwani 在
 * 《数据流的近似频率计数》一文中提出的，该文在 2002 年 8 月于中国香港举行的第 28 届国际大型数据
 * 库会议上发表，具体见第 4.2 节。该论文可在 http://www.vldb.org/conf/2002/S10P03.pdf 找到。
 *
 * Lossy Counting（也称为 LC）算法如下：
 * 设 s 是项目的阈值频率（我们感兴趣的最小频率），epsilon 是频率的误差范围。
 * 设 D 为一个三元组集合 (e, f, delta)，其中 e 为元素值，f 为该元素的频率（实际上是
 * 当前的出现计数），而 delta 是 f 的最大误差。我们首先使 D 为空，并以
 * 批次大小为 w 处理元素。（批次大小也称为 “桶大小”，等于 1/epsilon。）
 * 设当前批次编号为 b_current，从 1 开始。对于每个元素 e，如果它已经在 D 中
 * 则增量其 f 计数，否则将一个新三元组 (e, 1, b_current - 1) 插入 D。
 * 处理完每个批次后，我们修剪 D，移除所有满足 f + delta <= b_current 的元素。
 * 算法结束后，我们抑制 D 中所有不满足 f >= (s - epsilon) * N 的元素，
 * 其中 N 是输入中元素的总数。我们以估计频率 f/N 输出剩余元素。
 * LC 论文证明该算法找到的所有元素的真实频率至少为 s，且没有频率被高估或低估超出 epsilon。
 * 此外，在对输入分布进行合理假设的情况下，所需的表大小不超过约 7 倍 w。
 *
 * 在没有合理依据的情况下，我们遵循 ts_typanalyze() 并使用参数 s = 0.07/K，epsilon = s/10。
 * 但我们不考虑停用词的修正，因为它们不适用于数组。这些参数使桶宽度 w = K/0.007，最大
 * 预期哈希表大小约为 1000 * K。
 *
 * 元素在数组中可能重复。由于重复项不会改变 <@、&& 或 @> 的行为，我们希望在每个数组中
 * 仅计数每个元素一次。因此，我们在完成的 pg_statistic 条目中存储每个元素的频率，
 * 作为所有包含它的非空行的比例。我们通过非空计数（nonnull_cnt）来划分原始计数以获得这些数字。
 */
static void fc_compute_array_stats(VacAttrStats *fc_stats, AnalyzeAttrFetchFunc fc_fetchfunc,
					int fc_samplerows, double fc_totalrows)
{
	ArrayAnalyzeExtraData *fc_extra_data;
	int			fc_num_mcelem;
	int			fc_null_elem_cnt = 0;
	int			fc_analyzed_rows = 0;

	/* 这是LC算法中的D。 */
	HTAB	   *fc_elements_tab;
	HASHCTL		fc_elem_hash_ctl;
	HASH_SEQ_STATUS fc_scan_status;

	/* 这是来自LC算法的当前桶编号 */
	int			fc_b_current;

	/* 这是来自LC算法的'w' */
	int			fc_bucket_width;
	int			fc_array_no;
	int64		fc_element_no;
	TrackItem  *fc_item;
	int			fc_slot_idx;
	HTAB	   *fc_count_tab;
	HASHCTL		fc_count_hash_ctl;
	DECountItem *fc_count_item;

	fc_extra_data = (ArrayAnalyzeExtraData *) fc_stats->extra_data;

	/*
	 * 调用 analyze.c 的标准分析函数，为列创建标量风格的统计信息。
	 * 它会期待自己的 extra_data 指针，因此暂时安装它。
	 */
	fc_stats->extra_data = fc_extra_data->std_extra_data;
	fc_extra_data->std_compute_stats(fc_stats, fc_fetchfunc, fc_samplerows, fc_totalrows);
	fc_stats->extra_data = fc_extra_data;

	/*
	 * 设置静态指针供子例程使用。我们等到这里是为了防止 std_compute_stats 以某种方式递归调用我们（可能不可能，但 ...）
	 */
	array_extra_data = fc_extra_data;

	/*
	 * 我们希望 MCELEM 数组中有 statistics_target * 10 个元素。
	 * 这个乘数相当任意，但旨在反映在 pg_statistic 中跟踪的单个元素数量应
	 * 超过简单标量列的值数量。
	 */
	fc_num_mcelem = fc_stats->attr->attstattarget * 10;

	/*
	 * 我们将桶宽度设置为 num_mcelem / 0.007，如上面评论所述。
	 */
	fc_bucket_width = fc_num_mcelem * 1000 / 7;

	/*
	 * 创建哈希表。它将位于本地内存中，因此我们不需要担心初始大小溢出。
	 * 同时，我们不需要关注锁定和内存管理。
	 */
	fc_elem_hash_ctl.keysize = sizeof(Datum);
	fc_elem_hash_ctl.entrysize = sizeof(TrackItem);
	fc_elem_hash_ctl.hash = fc_element_hash;
	fc_elem_hash_ctl.match = fc_element_match;
	fc_elem_hash_ctl.hcxt = CurrentMemoryContext;
	fc_elements_tab = hash_create("Analyzed elements table",
							   fc_num_mcelem,
							   &fc_elem_hash_ctl,
							   HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT);

	/* 哈希表用于数组不同元素计数 */
	fc_count_hash_ctl.keysize = sizeof(int);
	fc_count_hash_ctl.entrysize = sizeof(DECountItem);
	fc_count_hash_ctl.hcxt = CurrentMemoryContext;
	fc_count_tab = hash_create("Array distinct element count table",
							64,
							&fc_count_hash_ctl,
							HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);

	/* 初始化计数器。 */
	fc_b_current = 1;
	fc_element_no = 0;

	/* 移动数组。 */
	for (fc_array_no = 0; fc_array_no < fc_samplerows; fc_array_no++)
	{
		Datum		fc_value;
		bool		fc_isnull;
		ArrayType  *fc_array;
		int			fc_num_elems;
		Datum	   *fc_elem_values;
		bool	   *fc_elem_nulls;
		bool		fc_null_present;
		int			fc_j;
		int64		fc_prev_element_no = fc_element_no;
		int			fc_distinct_count;
		bool		fc_count_item_found;

		vacuum_delay_point();

		fc_value = fc_fetchfunc(fc_stats, fc_array_no, &fc_isnull);
		if (fc_isnull)
		{
			/* 忽略整体为 null 的数组 */
			continue;
		}

		/* 跳过过大的值。 */
		if (toast_raw_datum_size(fc_value) > ARRAY_WIDTH_THRESHOLD)
			continue;
		else
			fc_analyzed_rows++;

		/* 
		 / 现在如有需要，解冻数组，并拆解为数据项。 
		 */
		fc_array = DatumGetArrayTypeP(fc_value);

		Assert(ARR_ELEMTYPE(fc_array) == fc_extra_data->type_id);
		deconstruct_array(fc_array,
						  fc_extra_data->type_id,
						  fc_extra_data->typlen,
						  fc_extra_data->typbyval,
						  fc_extra_data->typalign,
						  &fc_elem_values, &fc_elem_nulls, &fc_num_elems);

		/* 
		 / 我们循环遍历数组中的元素，并将其添加到我们的 
		 / 跟踪哈希表。 
		 */
		fc_null_present = false;
		for (fc_j = 0; fc_j < fc_num_elems; fc_j++)
		{
			Datum		fc_elem_value;
			bool		fc_found;

			/* 除了设置标志外，没有处理 null 元素 */
			if (fc_elem_nulls[fc_j])
			{
				fc_null_present = true;
				continue;
			}

			/* 在哈希表中查找当前元素，如果是新元素则添加它 */
			fc_elem_value = fc_elem_values[fc_j];
			fc_item = (TrackItem *) hash_search(fc_elements_tab,
											 (const void *) &fc_elem_value,
											 HASH_ENTER, &fc_found);

			if (fc_found)
			{
				/* 元素值已经在跟踪列表中 */

				/* 
				 / 我们帮助的操作符会忽略重复的数组元素，因此 
				 / 每个数组只统计一次给定的不同元素。 
				 */
				if (fc_item->last_container == fc_array_no)
					continue;

				fc_item->frequency++;
				fc_item->last_container = fc_array_no;
			}
			else
			{
				/* 初始化新的跟踪列表元素 */

				/* 
				 / 如果元素类型是传引用，则必须将其复制到 
				 / palloc 的空间中，以便我们可以在下面释放数组。（我们 
				 / 这样做是为了限制元素值所需的空间 
				 / 由哈希表的大小决定；如果我们保留所有的 
				 / 数组值，可能会更多。） 
				 */
				fc_item->key = datumCopy(fc_elem_value,
									  fc_extra_data->typbyval,
									  fc_extra_data->typlen);

				fc_item->frequency = 1;
				fc_item->delta = fc_b_current - 1;
				fc_item->last_container = fc_array_no;
			}

			/* element_no 是处理的元素数量（即 N） */
			fc_element_no++;

			/* 我们在处理每个桶后修剪D结构 */
			if (fc_element_no % fc_bucket_width == 0)
			{
				fc_prune_element_hashtable(fc_elements_tab, fc_b_current);
				fc_b_current++;
			}
		}

		/* 每个数组仅统计一次 null 元素的存在。 */
		if (fc_null_present)
			fc_null_elem_cnt++;

		/* 更新特定数组的不同元素计数频率。 */
		fc_distinct_count = (int) (fc_element_no - fc_prev_element_no);
		fc_count_item = (DECountItem *) hash_search(fc_count_tab, &fc_distinct_count,
												 HASH_ENTER,
												 &fc_count_item_found);

		if (fc_count_item_found)
			fc_count_item->frequency++;
		else
			fc_count_item->frequency = 1;

		/* 释放解冻时分配的内存。 */
		if (PointerGetDatum(fc_array) != fc_value)
			pfree(fc_array);
		pfree(fc_elem_values);
		pfree(fc_elem_nulls);
	}

	/* 跳过被标准统计占用的 pg_statistic 插槽 */
	fc_slot_idx = 0;
	while (fc_slot_idx < STATISTIC_NUM_SLOTS && fc_stats->stakind[fc_slot_idx] != 0)
		fc_slot_idx++;
	if (fc_slot_idx > STATISTIC_NUM_SLOTS - 2)
		elog(ERROR, "insufficient pg_statistic slots for array stats");

	/* 只有在找到一些非空值的情况下，我们才能计算真实的统计数据。 */
	if (fc_analyzed_rows > 0)
	{
		int			fc_nonnull_cnt = fc_analyzed_rows;
		int			fc_count_items_count;
		int			fc_i;
		TrackItem **sort_table;
		int			fc_track_len;
		int64		fc_cutoff_freq;
		int64		fc_minfreq,
					fc_maxfreq;

		/*
		 * 我们假设标准统计代码已经处理了设置
		 * stats_valid, stanullfrac, stawidth, stadistinct。如果我们想要不存储标准
		 * 统计数据，就必须重新计算这些值。
		 */

		/*
		 * 构建一个有趣的哈希表项数组，即
		 * 那些满足截止频率(s - epsilon)*N的项。还要识别
		 * 这些项中的最小和最大频率。
		 *
		 * 由于epsilon = s/10且bucket_width = 1/epsilon，因此截止
		 * 频率为9*N / bucket_width。
		 */
		fc_cutoff_freq = 9 * fc_element_no / fc_bucket_width;

		fc_i = hash_get_num_entries(fc_elements_tab); /* 足够的空间 */
		sort_table = (TrackItem **) palloc(sizeof(TrackItem *) * fc_i);

		hash_seq_init(&fc_scan_status, fc_elements_tab);
		fc_track_len = 0;
		fc_minfreq = fc_element_no;
		fc_maxfreq = 0;
		while ((fc_item = (TrackItem *) hash_seq_search(&fc_scan_status)) != NULL)
		{
			if (fc_item->frequency > fc_cutoff_freq)
			{
				sort_table[fc_track_len++] = fc_item;
				fc_minfreq = Min(fc_minfreq, fc_item->frequency);
				fc_maxfreq = Max(fc_maxfreq, fc_item->frequency);
			}
		}
		Assert(fc_track_len <= fc_i);

		/* 输出一些用于调试的统计信息 */
		elog(DEBUG3, "compute_array_stats: target # mces = %d, "
			 "bucket width = %d, "
			 "# elements = " INT64_FORMAT ", hashtable size = %d, "
			 "usable entries = %d",
			 fc_num_mcelem, fc_bucket_width, fc_element_no, fc_i, fc_track_len);

		/*
		 * 如果我们获得的元素数量超过了实际需要的数量，那么去掉那些
		 * 出现频率最低的元素。最简单的方法是对数组进行降序排序
		 * 并截断数组。
		 */
		if (fc_num_mcelem < fc_track_len)
		{
			qsort_interruptible(sort_table, fc_track_len, sizeof(TrackItem *),
								fc_trackitem_compare_frequencies_desc, NULL);
			/* 将minfreq重置为我们保留的最小频率 */
			fc_minfreq = sort_table[fc_num_mcelem - 1]->frequency;
		}
		else
			fc_num_mcelem = fc_track_len;

		/* 生成MCELEM插槽条目 */
		if (fc_num_mcelem > 0)
		{
			MemoryContext fc_old_context;
			Datum	   *fc_mcelem_values;
			float4	   *fc_mcelem_freqs;

			/*
			 * 我们希望存储根据元素值排序的统计信息，使用
			 * 元素类型的默认比较函数。这允许
			 * 在选择性估计函数中进行快速的二分查找。
			 */
			qsort_interruptible(sort_table, fc_num_mcelem, sizeof(TrackItem *),
								fc_trackitem_compare_element, NULL);

			/* 必须将目标值复制到anl_context中 */
			fc_old_context = MemoryContextSwitchTo(fc_stats->anl_context);

			/*
			 * 我们按照元素值对统计信息进行了排序，但我们希望能够
			 * 找到最小和最大频率，而无需检查所有值。
			 * 我们还希望获得空元素的频率。将这三个值存储在mcelem_freqs的末尾。
			 */
			fc_mcelem_values = (Datum *) palloc(fc_num_mcelem * sizeof(Datum));
			fc_mcelem_freqs = (float4 *) palloc((fc_num_mcelem + 3) * sizeof(float4));

			/*
			 * 请参见上面的评论，以非空计数作为最终频率估计的除数。
			 */
			for (fc_i = 0; fc_i < fc_num_mcelem; fc_i++)
			{
				TrackItem  *fc_item = sort_table[fc_i];

				fc_mcelem_values[fc_i] = datumCopy(fc_item->key,
											 fc_extra_data->typbyval,
											 fc_extra_data->typlen);
				fc_mcelem_freqs[fc_i] = (double) fc_item->frequency /
					(double) fc_nonnull_cnt;
			}
			fc_mcelem_freqs[fc_i++] = (double) fc_minfreq / (double) fc_nonnull_cnt;
			fc_mcelem_freqs[fc_i++] = (double) fc_maxfreq / (double) fc_nonnull_cnt;
			fc_mcelem_freqs[fc_i++] = (double) fc_null_elem_cnt / (double) fc_nonnull_cnt;

			MemoryContextSwitchTo(fc_old_context);

			fc_stats->stakind[fc_slot_idx] = STATISTIC_KIND_MCELEM;
			fc_stats->staop[fc_slot_idx] = fc_extra_data->eq_opr;
			fc_stats->stacoll[fc_slot_idx] = fc_extra_data->coll_id;
			fc_stats->stanumbers[fc_slot_idx] = fc_mcelem_freqs;
			/* 请参见上面的关于额外stanumber条目的注释 */
			fc_stats->numnumbers[fc_slot_idx] = fc_num_mcelem + 3;
			fc_stats->stavalues[fc_slot_idx] = fc_mcelem_values;
			fc_stats->numvalues[fc_slot_idx] = fc_num_mcelem;
			/* 我们正在存储元素类型的值 */
			fc_stats->statypid[fc_slot_idx] = fc_extra_data->type_id;
			fc_stats->statyplen[fc_slot_idx] = fc_extra_data->typlen;
			fc_stats->statypbyval[fc_slot_idx] = fc_extra_data->typbyval;
			fc_stats->statypalign[fc_slot_idx] = fc_extra_data->typalign;
			fc_slot_idx++;
		}

		/* 生成DECHIST槽条目 */
		fc_count_items_count = hash_get_num_entries(fc_count_tab);
		if (fc_count_items_count > 0)
		{
			int			fc_num_hist = fc_stats->attr->attstattarget;
			DECountItem **fc_sorted_count_items;
			int			fc_j;
			int			fc_delta;
			int64		fc_frac;
			float4	   *fc_hist;

			/* num_hist必须至少为2，以便下面的循环正常工作 */
			fc_num_hist = Max(fc_num_hist, 2);

			/*
			 * 创建一个DECountItem指针的数组，并按照
			 * 计数的递增顺序对其进行排序。
			 */
			fc_sorted_count_items = (DECountItem **)
				palloc(sizeof(DECountItem *) * fc_count_items_count);
			hash_seq_init(&fc_scan_status, fc_count_tab);
			fc_j = 0;
			while ((fc_count_item = (DECountItem *) hash_seq_search(&fc_scan_status)) != NULL)
			{
				fc_sorted_count_items[fc_j++] = fc_count_item;
			}
			qsort_interruptible(fc_sorted_count_items, fc_count_items_count,
								sizeof(DECountItem *),
								fc_countitem_compare_count, NULL);

			/*
			 * 准备用直方图填充stanumbers，后跟
			 * 平均计数。此数组必须存储在anl_context中。
			 */
			fc_hist = (float4 *)
				MemoryContextAlloc(fc_stats->anl_context,
								   sizeof(float4) * (fc_num_hist + 1));
			fc_hist[fc_num_hist] = (double) fc_element_no / (double) fc_nonnull_cnt;

			/*----------
			 * 构建不同元素计数（DEC）的直方图。
			 *
			 * 此循环的目的是将最小和最大DEC复制到
			 * hist[0]和hist[num_hist - 1]，以及之间均匀间隔的DEC
			 * (在此“均匀间隔”是相对于
			 * 整个输入数组的种群而言)。如果我们有一个完整的已排序
			 * 的DEC数组，每个分析过的行一个，那么第i个hist值将
			 * 来自DEC[i * (analyzed_rows - 1) / (num_hist - 1)]
			 * (比较compute_scalar_stats()中的直方图生成循环)。
			 * 但我们有的是sorted_count_items[]数组，
			 * 该数组持有独特的DEC值及其频率（即，
			 * 全数组的运行长度压缩版本）。因此我们
			 * 通过变量“frac”控制前进，该变量定义为(x - y) * (num_hist - 1)，
			 * 其中x是对应于下一个sorted_count_items[]元素的运行开始的
			 * 理论DEC数组中的索引，y是我们应该取下一个
			 * 直方图值的DEC索引。每当x <= y时，我们都必须前进，
			 * 即frac <= 0。x分量是到目前为止看到的频率之和
			 * （经过当前的sorted_count_items[]元素），
			 * 当然y * (num_hist - 1) = i * (analyzed_rows - 1)，
			 * 根据上面的下标计算。 （下标计算
			 * 意味着丢弃y的任何小数部分；在此公式中
			 * 处理这个问题的方法是不前进，直到frac达到1。）
			 *
			 * 即使frac有一个有限范围，在处理非常大的统计目标时，它也可能溢出int32，
			 * 因此我们在int64中进行数学运算。
			 *----------
			 */
			fc_delta = fc_analyzed_rows - 1;
			fc_j = 0;				/* sorted_count_items中的当前索引 */
			/* 初始化sorted_count_items[0]的frac；y最初为0 */
			fc_frac = (int64) fc_sorted_count_items[0]->frequency * (fc_num_hist - 1);
			for (fc_i = 0; fc_i < fc_num_hist; fc_i++)
			{
				while (fc_frac <= 0)
				{
					/* 前进，并更新frac的x分量 */
					fc_j++;
					fc_frac += (int64) fc_sorted_count_items[fc_j]->frequency * (fc_num_hist - 1);
				}
				fc_hist[fc_i] = fc_sorted_count_items[fc_j]->count;
				fc_frac -= fc_delta;	/* 更新即将到来的i增量的y */
			}
			Assert(fc_j == fc_count_items_count - 1);

			fc_stats->stakind[fc_slot_idx] = STATISTIC_KIND_DECHIST;
			fc_stats->staop[fc_slot_idx] = fc_extra_data->eq_opr;
			fc_stats->stacoll[fc_slot_idx] = fc_extra_data->coll_id;
			fc_stats->stanumbers[fc_slot_idx] = fc_hist;
			fc_stats->numnumbers[fc_slot_idx] = fc_num_hist + 1;
			fc_slot_idx++;
		}
	}

	/*
	 * 我们不需要清理任何临时的 palloc。哈希表也应该被清除，因为它使用了子内存上下文。
	 */
}

/*
 * 一个用于修剪来自Lossy Counting算法的D结构的函数。
 * 请参考compute_tsvector_stats()以获取更广泛的解释。
 */
static void fc_prune_element_hashtable(HTAB *fc_elements_tab, int fc_b_current)
{
	HASH_SEQ_STATUS fc_scan_status;
	TrackItem  *fc_item;

	hash_seq_init(&fc_scan_status, fc_elements_tab);
	while ((fc_item = (TrackItem *) hash_seq_search(&fc_scan_status)) != NULL)
	{
		if (fc_item->frequency + fc_item->delta <= fc_b_current)
		{
			Datum		fc_value = fc_item->key;

			if (hash_search(fc_elements_tab, (const void *) &fc_item->key,
							HASH_REMOVE, NULL) == NULL)
				elog(ERROR, "hash table corrupted");
			/* 如果元素不是通过值传递的，则应该释放内存 */
			if (!array_extra_data->typbyval)
				pfree(DatumGetPointer(fc_value));
		}
	}
}

/*
 * 元素的哈希函数。
 *
 * 我们使用元素类型的默认哈希操作类，如果该类型对排序敏感，则使用列排序。
 */
static uint32 fc_element_hash(const void *fc_key, Size fc_keysize)
{
	Datum		fc_d = *((const Datum *) fc_key);
	Datum		fc_h;

	fc_h = FunctionCall1Coll(array_extra_data->hash,
						  array_extra_data->coll_id,
						  fc_d);
	return DatumGetUInt32(fc_h);
}

/*
 * 元素的匹配函数，用于哈希表查找。
 */
static int fc_element_match(const void *fc_key1, const void *fc_key2, Size fc_keysize)
{
	/* keysize参数在这里是多余的 */
	return fc_element_compare(fc_key1, fc_key2);
}

/*
 * 元素的比较函数。
 *
 * 我们使用元素类型的默认btree操作类，如果该类型对排序敏感，则使用列排序。
 *
 * XXX考虑使用SortSupport基础设施
 */
static int fc_element_compare(const void *fc_key1, const void *fc_key2)
{
	Datum		fc_d1 = *((const Datum *) fc_key1);
	Datum		fc_d2 = *((const Datum *) fc_key2);
	Datum		fc_c;

	fc_c = FunctionCall2Coll(array_extra_data->cmp,
						  array_extra_data->coll_id,
						  fc_d1, fc_d2);
	return DatumGetInt32(fc_c);
}

/*
 * 用于按频率排序TrackItems的比较器（降序排序）
 */
static int fc_trackitem_compare_frequencies_desc(const void *fc_e1, const void *fc_e2, void *fc_arg)
{
	const TrackItem *const *fc_t1 = (const TrackItem *const *) fc_e1;
	const TrackItem *const *fc_t2 = (const TrackItem *const *) fc_e2;

	return (*fc_t2)->frequency - (*fc_t1)->frequency;
}

/*
 * 用于按元素值排序TrackItems的比较器
 */
static int fc_trackitem_compare_element(const void *fc_e1, const void *fc_e2, void *fc_arg)
{
	const TrackItem *const *fc_t1 = (const TrackItem *const *) fc_e1;
	const TrackItem *const *fc_t2 = (const TrackItem *const *) fc_e2;

	return fc_element_compare(&(*fc_t1)->key, &(*fc_t2)->key);
}

/*
 * 按计数对DECountItems进行排序的比较器
 */
static int fc_countitem_compare_count(const void *fc_e1, const void *fc_e2, void *fc_arg)
{
	const DECountItem *const *fc_t1 = (const DECountItem *const *) fc_e1;
	const DECountItem *const *fc_t2 = (const DECountItem *const *) fc_e2;

	if ((*fc_t1)->count < (*fc_t2)->count)
		return -1;
	else if ((*fc_t1)->count == (*fc_t2)->count)
		return 0;
	else
		return 1;
}
